package com.sunny.t3;

// IMPORT LIBRARY PACKAGES NEEDED BY YOUR PROGRAM
import java.util.List;
import java.util.*;
// SOME CLASSES WITHIN A PACKAGE MAY BE RESTRICTED
// DEFINE ANY CLASS AND METHOD NEEDED
// CLASS BEGINS, THIS CLASS IS REQUIRED
class Solution
{
    // METHOD SIGNATURE BEGINS, THIS METHOD IS REQUIRED
    List<Integer> salaryfrequeny(int num, int[] salaries)
    {
        // WRITE YOUR CODE HERE
        ArrayList<Integer> res = new ArrayList<>();
        HashMap<Integer,Integer> map = new HashMap<>();
        HashMap<Integer,Integer> umap = new HashMap<>();
        for(int i=0;i<num;i++){
            int sal = salaries[i];
            if(map.containsKey(sal)){
                map.put(sal, map.get(sal)+1);
            }else{
                umap.put(sal,i);
                map.put(sal,1);
            }
        }
        ArrayList<Node> l = new ArrayList<>();
        for(Map.Entry<Integer,Integer> entry: map.entrySet()){
            int sal = entry.getKey();
            int n = entry.getValue();
            int first = umap.get(sal);
            Node tmp = new Node(sal, first, n);
            l.add(tmp);
        }
        Collections.sort(l);
        for(int i=0;i<l.size();i++){
            for(int j=0;j<l.get(i).num;j++){
                res.add(l.get(i).sal);
            }
        }
        return res;
    }
    // METHOD SIGNATURE ENDS
    class Node implements Comparable<Node> {
        int sal;
        int first;
        int num;
        public Node(int sal, int first, int num){
            this.sal = sal;
            this.first = first;
            this.num = num;
        }
        @Override
        public int compareTo(Node o) {
            if(this.num == o.num)
                return this.first-o.first;
            return o.num - this.num;
        }
    }
}
